﻿#pragma once
#include"global.h"
#include"lexer.h"
using namespace std;

// 定义文法符号类型
enum SymbolType {
    TERMINAL,
    NON_TERMINAL
};

// 文法符号
struct Symbol {
    string name;
    SymbolType type;
    Symbol()
    {

    }
    Symbol(string s, SymbolType tp)
    {
        name = s;
        type = tp;
    }
    bool operator==(const Symbol& other) const {
        return name == other.name && type == other.type;
    }
    bool operator!=(const Symbol& other) const {
        return name != other.name;
    }
    bool operator<(const Symbol& other) const {
        if (type != other.type) return type < other.type;
        return name < other.name;
    }

  // 在Symbol结构体定义中添加
    string serialize() const {
        return name + "@" + to_string(type);  // 使用制表符分隔
    }

    static Symbol deserialize(const string& str) {
        size_t pos = str.find('@');
        if (pos == string::npos) return Symbol();
        return Symbol(str.substr(0, pos), static_cast<SymbolType>(stoi(str.substr(pos + 1))));
    }


};

// 哈希函数特化
namespace std {
    template<>
    struct hash<Symbol> {
        size_t operator()(const Symbol& s) const {
            return hash<string>()(s.name) ^ hash<int>()(static_cast<int>(s.type));
        }
    };
}

// 产生式
struct Production {
    Symbol left;
    vector<Symbol> right;
    vector<string> semanticAction;

    string toString() const {
        stringstream ss;
        ss << left.name << " -> ";
        for (const auto& s : right) {
            ss << s.name << " ";
        }
        return ss.str();
    }
    // 在Production结构体定义中添加
    string serialize() const {
        stringstream ss;
        ss << left.serialize() << "\n";  // 第一行是左部

        // 第二行是右部符号，用逗号分隔
        for (size_t i = 0; i < right.size(); ++i) {
            if (i != 0) ss << "#";
            ss << right[i].serialize();
        }
        ss << "\n";

        // 第三行是语义动作，用逗号分隔
        for (size_t i = 0; i < semanticAction.size(); ++i) {
            if (i != 0) ss << "#";
            ss << semanticAction[i];
        }

        return ss.str();
    }

    static Production deserialize(const vector<string>& lines) {
        Production p;
        if (lines.size() < 2) return p;  // 至少需要左部和右部

        // 解析左部
        p.left = Symbol::deserialize(lines[0]);

        // 解析右部
        stringstream rightSS(lines[1]);
        string symbolStr;
        while (getline(rightSS, symbolStr, '#')) {
            if (!symbolStr.empty()) {
                p.right.push_back(Symbol::deserialize(symbolStr));
            }
        }

        // 解析语义动作（如果有）
        if (lines.size() > 2) {
            stringstream actionSS(lines[2]);
            string action;
            while (getline(actionSS, action, '#')) {
                if (!action.empty()) {
                    p.semanticAction.push_back(action);
                }
            }
        }

        return p;
    }

};

// LR(1)项
struct LR1Item {
    Production production;
    int dotPos;
    Symbol lookahead;

    bool operator==(const LR1Item& other) const {
        return production.toString() == other.production.toString() &&
            dotPos == other.dotPos &&
            lookahead.name == other.lookahead.name;
    }

    bool operator<(const LR1Item& other) const {
        if (production.toString() != other.production.toString())
            return production.toString() < other.production.toString();
        if (dotPos != other.dotPos)
            return dotPos < other.dotPos;
        return lookahead.name < other.lookahead.name;
    }

    string toString() const {
        stringstream ss;
        ss << "[" << production.left.name << " -> ";
        for (int i = 0; i < production.right.size(); i++) {
            if (i == dotPos) ss << "• ";
            ss << production.right[i].name << " ";
        }
        if (dotPos == production.right.size()) ss << "•";
        ss << ", " << lookahead.name << "]";
        return ss.str();
    }

    bool isDotAtEnd() const {
        return dotPos == production.right.size();
    }

    Symbol nextSymbol() const {
        if (dotPos >= production.right.size()) return Symbol("", TERMINAL);
        return production.right[dotPos];
    }
    // 在LR1Item结构体定义中添加
    string serialize() const {
        stringstream ss;
        ss << production.serialize() << "\n";
        ss << dotPos << "\n";
        ss << lookahead.serialize();
        return ss.str();
    }

    static LR1Item deserialize(const vector<string>& lines) {
        LR1Item item;
        if (lines.size() < 3) return item;

        // 解析产生式（可能跨多行）
        vector<string> prodLines;
        size_t i = 0;
        while (i < 3) {
            prodLines.push_back(lines[i++]);
        }
        item.production = Production::deserialize(prodLines);

        // 解析dotPos
        if (i < lines.size()) {
            item.dotPos = stoi(lines[i++]);
        }

        // 解析展望符
        if (i < lines.size()) {
            item.lookahead = Symbol::deserialize(lines[i]);
        }

        return item;
    }


};

// LR(1)项集
struct LR1ItemSet {
    set<LR1Item> items;
    int id;

    bool operator==(const LR1ItemSet& other) const {
        return items == other.items;
    }

    string toString() const {
        stringstream ss;
        ss << "I" << id << ":\n";
        for (const auto& item : items) {
            ss << "  " << item.toString() << "\n";
        }
        return ss.str();
    }
    // 在LR1ItemSet结构体定义中添加
    string serialize() const {
        stringstream ss;
        ss << id << "\n";
        ss << items.size() << "\n";
        for (const auto& item : items) {
            ss << item.serialize() << "\n---\n";  // 用---分隔不同项
        }
        return ss.str();
    }

    static LR1ItemSet deserialize(const vector<string>& lines) {
        LR1ItemSet itemSet;
        if (lines.size() < 2) return itemSet;

        // 解析ID
        itemSet.id = stoi(lines[0]);

        // 解析项数量
        int itemCount = stoi(lines[1]);

        // 解析各个项
        vector<string> currentItemLines;
        for (size_t i = 2; i < lines.size(); ++i) {
            if (lines[i] == "---") {
                if (!currentItemLines.empty()) {
                    itemSet.items.insert(LR1Item::deserialize(currentItemLines));
                    currentItemLines.clear();
                }
            }
            else {
                currentItemLines.push_back(lines[i]);
            }
        }

        // 检查项数量是否匹配
        if (itemSet.items.size() != itemCount) {
            cerr << "Warning: Item count mismatch, expected " << itemCount
                << ", got " << itemSet.items.size() << endl;
        }

        return itemSet;
    }


};

// LR(1)分析表动作
enum ActionType {
    SHIFT,
    REDUCE,
    ACCEPT,
    ERROR
};

struct Action {
    ActionType type;
    int target; // 对于SHIFT是状态号，对于REDUCE是产生式号

    string toString() const {
        switch (type) {
        case SHIFT: return "s" + to_string(target);
        case REDUCE: return "r" + to_string(target);
        case ACCEPT: return "acc";
        default: return "err";
        }
    }
};

// LR(1)分析表
struct LR1ParsingTable {
    vector<map<Symbol, Action>> actionTable;
    vector<map<Symbol, int>> gotoTable;

    void print() const {
        cout << "LR(1) Parsing Table:\n";
        cout << "State\tAction\t\tGoto\n";

        // 收集所有符号
        set<Symbol> allSymbols;
        for (const auto& state : actionTable) {
            for (const auto& entry : state) {
                allSymbols.insert(entry.first);
            }
        }

        for (size_t i = 0; i < actionTable.size(); i++) {
            cout << i << "\t";

            // 打印动作部分
            bool first = true;
            for (const auto& sym : allSymbols) {
                if (sym.type != TERMINAL) continue;

                auto it = actionTable[i].find(sym);
                if (it != actionTable[i].end()) {
                    if (!first) cout << ", ";
                    cout << sym.name << ":" << it->second.toString();
                    first = false;
                }
            }

            cout << "\t\t";

            // 打印goto部分
            first = true;
            for (const auto& sym : allSymbols) {
                if (sym.type != NON_TERMINAL) continue;

                auto it = gotoTable[i].find(sym);
                if (it != gotoTable[i].end()) {
                    if (!first) cout << ", ";
                    cout << sym.name << ":" << it->second;
                    first = false;
                }
            }

            cout << "\n";
        }
    }
};

enum VarType { TYPE_INT, TYPE_DOUBLE, TYPE_UNKNOWN };

struct SymbolTableEntry {
	string name;
	VarType type; // 0 for int, 1 for double
	// string value; // Value is not used at compile time per requirements
	int offset;

	SymbolTableEntry(string n, VarType t, int o)
		: name(n), type(t), offset(o) {}

	// Default constructor for placeholder entries if needed
	SymbolTableEntry() : name(""), type(TYPE_UNKNOWN), offset(-1) {}
};

class SymbolTable {
public:
	vector<SymbolTableEntry> entries;
	map<string, int> nameToIndex; // Faster lookups by name
	int currentOffset = 0;
	int tempCount = 0;
	bool errorOccurred = false; // Flag for duplicate definitions

	// Returns index if successful, -1 if duplicate, sets errorOccurred
	int addEntry(const string& name, VarType type) {
		if (nameToIndex.count(name)) {
			cout << "Syntax Error" << endl; exit(0); // Duplicate definition error
			errorOccurred = true;
			return -1;
		}
		int width = (type == TYPE_INT) ? 4 : 8;
		entries.emplace_back(name, type, currentOffset);
		int index = entries.size() - 1;
		nameToIndex[name] = index;
		currentOffset += width;
		return index;
	}

	// Returns index or -1 if not found
	int lookupIndex(const string& name) const {
		auto it = nameToIndex.find(name);
		if (it != nameToIndex.end()) {
			return it->second;
		}
		return -1; // Not found
	}

	// Returns "TB<index>" or "" if not found
	string lookupPlace(const string& name) const {
		int index = lookupIndex(name);
		if (index != -1) {
			return "TB" + to_string(index);
		}
		cout << "Syntax Error" << endl; exit(0); // Undefined variable error
		// errorOccurred = true; // Optionally set error flag here too
		return ""; // Indicate error
	}

	// Returns type or TYPE_UNKNOWN if not found
	VarType lookupType(const string& name) const {
		int index = lookupIndex(name);
		if (index != -1) {
			return entries[index].type;
		}
		// Error should have been caught by lookupPlace typically
		return TYPE_UNKNOWN;
	}

	string newTemp(VarType type) {
		// Ensure temporary variables are also somehow recorded if needed later,
		// although the current requirement seems to just need the name format.
		string temp = "T" + to_string(tempCount++) + (type == TYPE_INT ? "_i" : "_d");
		return temp;
	}

	void print() const {
		cout << entries.size() << endl;
		for (const auto& entry : entries) {
			cout << entry.name << " "
				<< (entry.type == TYPE_INT ? 0 : 1) << " "
				<< "null" << " " // Value is always null
				<< entry.offset << endl;
		}
		cout << tempCount << endl; // Output total temp vars used
	}

	int getWidth(VarType type) const {
		return (type == TYPE_INT) ? 4 : 8;
	}

	VarType getTypeFromPlace(const string& place) const {
		if (place.empty()) return TYPE_UNKNOWN;
		if (place[0] == 'T' && place.find('_') != string::npos) {
			return (place.back() == 'i') ? TYPE_INT : TYPE_DOUBLE;
		}
		if (place.substr(0, 2) == "TB") {
			try {
				int index = stoi(place.substr(2));
				if (index >= 0 && index < entries.size()) {
					return entries[index].type;
				}
			}
			catch (...) {
				// Handle potential stoi error
			}
		}
		// Could be a literal, need more context, or handle error
		return TYPE_UNKNOWN;
	}
};

// --- Quadruples ---
struct Quadruple {
	string op;
	string arg1;
	string arg2;
	string result;

	// Default constructor
	Quadruple() : op(""), arg1(""), arg2(""), result("") {}


	Quadruple(string o, string a1, string a2, string r)
		: op(move(o)), arg1(move(a1)), arg2(move(a2)), result(move(r)) {}

	string toString() const {
		// Handle potential floating point formatting for arg1 if needed
		// This basic version assumes args are strings already formatted.
		// Need specific logic if arg1 can be a raw double value passed here.
		stringstream ss;
		ss << "(" << op << "," << arg1 << "," << arg2 << "," << result << ")";
		return ss.str();
	}
};

// --- Backpatching ---
using PatchList = list<int>; // List of quadruple indices to patch


// --- Attribute Type ---
// Structure to hold attributes for symbols on the semantic stack
struct Attributes {
	string name = "";         // For ID, potentially others
	string place = "";        // For EXPR, ITEM, FACTOR, BFACTOR, etc.
	VarType type = TYPE_UNKNOWN; // For T, EXPR, ITEM, FACTOR, VARIABLE, BFACTOR, etc.
	int width = 0;           // For T, VARIABLE
	string op = "";           // For PLUS_MINUS, MUL_DIV, REL
	int quad = -1;           // For M, N (start address of code)
	PatchList truelist;      // For B, BANDTERM, BORTERM
	PatchList falselist;     // For B, BANDTERM, BORTERM
	PatchList nextlist;      // For STATEMENT, L

	// Default constructor
	Attributes() = default;
};





class Lexer;  // 前向声明


// 文法类
class Grammar {
public:
    vector<Production> productions;
    Symbol startSymbol;
    unordered_set<Symbol> terminals;
    unordered_set<Symbol> nonTerminals;



    Grammar(string inputfile);
    void addProduction(const Production& p);

    void setStartSymbol(const Symbol& s);

    void computeFirstSets();

    set<Symbol> computeFirst(const vector<Symbol>& symbols);

    void printFirstSets() ;

    vector<LR1ItemSet> buildLR1ItemSets();

    LR1ParsingTable buildLR1ParsingTable(const vector<LR1ItemSet>& itemSets);
	
	// ... (existing members) ...
	bool parse(Lexer& lexer, const LR1ParsingTable& table); // Add parse method

   
	void printQuads() const; // Helper to print quads
    void serializeTransitions(ofstream& out) const;
    void deserializeTransitions(ifstream& in);
	

private:
    unordered_map<Symbol, set<Symbol>> first;
    map<pair<int, Symbol>, int> transitions; // (fromState, symbol) -> toState
    map<pair<int, Symbol>, int> nonTerminalTransitions;

    void closure(LR1ItemSet& itemSet);

    void gotoFunction(const LR1ItemSet& I, Symbol X, LR1ItemSet& newSet);
	
	// ... (existing members) ...
	// Add a stack for semantic attributes
	stack<Attributes> attributeStack;
	// Helper function for semantic actions during reduction
//	bool executeSemanticAction(int productionIndex, const vector<Symbol>& rhsSymbols, const vector<Token>& rhsTokens); // Pass RHS tokens if needed
	bool executeSemanticAction(int productionIndex, const vector<Attributes>& rhsAttrs, Attributes& lhsAttrs);
	// Map terminal name back to Symbol object
	Symbol findTerminalSymbol(const string& name) const;
	Symbol findNonTerminalSymbol(const string& name) const;

	// Add semantic action helper functions specific to the parser if needed
	bool checkTypes(const string& place1, const string& place2, const string& operation,string result);

    //void serializeFirstSets(ofstream& out) const;
   // void deserializeFirstSets(ifstream& in);
};
